\section{Search}
\begin{description}
	\item[Question 1] exercise 3.5 (4 points)\\
	Consider the \(n\)-queens problem using the ''efficient''
	incremental formulation given on page 67. Explain why the
	state space size is at least \(\sqrt[3]{n!}\) and estimate
	the largest \(n\) for which exhaustive exploration is
	feasible. (\emph{Hint:} Derive a lower bound on the branching
	factor by considering the maximum number of squares that a
	queen can attack in any column.)% p 117

	\item[Question 2] exercise 4.1 (5 points)\\
	Trace the operation of A\(^*\) search applied to the problem
	of getting to Bucharest from Lugoj using the straight-line
	distance heuristic. That is, show the sequence of nodes that
    the algorithm will consider and the $f$, $g$ and $h$ score for
    each node.

	\item[Question 3] exercise 4.11 a, b and d (3 points)\\
	Give the name of the algorithm that results from each of the following spacial cases:\\
	a) Local beam search with \(k=1\).\\
	b) Local beam search with one initial state and no limit on the number of states retained.\\
	d) Genetic algorithm with population size \(N=1\).

	\item[Question 4] Cryptarithmetic puzzle (3 points).\\
    Cryptarithmetic problems are defined as follows
	(see course book, page 140): Each letter should be assigned a
	distinct digit such that the resulting sum is arithmetically
	correct with the additional restriction that no leading zeros
	are allowed.\\

    HELP + FAME = FALEC\\ 

    Write down the solution and explain briefly
    your solution method (you may choose any method that you find suitable
    including software packages).

\end{description}

\subsection{Answer 1}
\subsubsection{State-space}
First we recognize that on any one row or column, we can place only one
queen. On a n-queen board, we have n rows. Let's consider the task of
placeing one queen in each row. In the first row we have $n$ options,
but in the next row, we might only have $n-3$ options. Other queens may
attack a maximum of three squares in the current row. That means that in
row $i$, we will have \emph{at least} $n-3i$ squares to choose from when
placing queen $i$. So the size of the state space, $S$ will be at least:

\begin{equation}
    S = n(n-3)(n-6)(n-9)...(n-3i)...
\end{equation}

We now se that by multiplying $S$ with two other similar series, $S_1$
and $S_2$,

\begin{equation}
    S_1 = (n-2)(n-5)(n-8)\ldots(n-3i+1)\ldots
\end{equation}
\begin{equation}
    S_2 = (n-1)(n-4)(n-7)\ldots(n-3i+2)\ldots
\end{equation}

we get:

\begin{equation}
n!
\end{equation}

And, since $S > S_1$ and $S > S_2$ we see that $S > \sqrt[3]{n!}$.

\subsubsection{Maximum problem size}
Using this incremental method gives us a state-space in the order
$\sqrt[3]{n!}$. Modern desktop computers have the capacity to do in the
order $10^{10}$ operations each second. Exploring one state certainly
requires more than one operation, but on the other hand we could
certainly wait more than one second. So, this method might be practiacal
for problems with up to 30 queens, where the state-space reaches the
order $10^{10}$.

\newpage
\subsection{Answer 2}
A\(^*\) with tree-search. In this method we allways choose to expand
(look at the neighbours) the tree-node, $n$ with the smallest $f(n)$
where $f(n)$ is based on both the shortest distance found so far,
$g(n)$ and the estimated distance left to travel given by the heuristic
function $h(n)$. A\(^*\) might be said to be dijkstras algorithm guided
by a heuristic function.

\begin{equation}
f(n) = g(n) + h(n)
\end{equation}

\subsubsection{The path from Lugoj to Bucharest}
% A* on p 97
% h on p 95
% g on p 63
\begin{verbatim}
n               g(n)    h(n)    f(n)
------------------------------------
Step 0:
Lugoj           0       244     244

Step 1:
Timisoara       111     329     440
Mehadia         70      241     311

Step 2: (expanding Mehadia)
Drobeta         145     242     387

Step 3: (expanding Drobeta)
Craiova         265     160     425

Step 4: (expanding Craiova)
Rimnicu Vilcea  411     193     604
Pitesti         403     100     503

Step 5: (expanding Timisoara)
Arad            229     366     595

Step 6: (expanding Pitesti)
Bucharest       504     0       504
\end{verbatim}

\subsection{Answer 3}
% p 115
\emph{Local beam search starts with $k$ random start states. It looks
at all the neighbouring states of these states and then pick the $k$
best successor states among all the neighbours.}\\

% p 117
\emph{Genetic algorithms work with a population of solutions and
gradually refine this population through evolution. An iteration
with a GA start with the fitnessevaluation of all solutions in the
population. Solutions with high fitnessvalue are then selected with high
probability to form the genetic material for the next generation. The
selected solutions undergo crossover (mating) to swap parts of each
solution with eachother. Finally, a small number of random mutations to
the population gives the ability to explore new solutions.}

\subsubsection{a)}
\emph{Hill-climbing search} also known as \emph{greedy local search}. We
start in one random start state, look at all the the neighbouring states
and continue our search in the direction of the best neighbour.

\subsubsection{b)}
\emph{Breadth-first search}. If we start in one state, look at all
neighbours, then continue to look at their neighbours etc, etc - then we
are doing breadth-first search.

\subsubsection{d)}
\emph{Random walk}. With only one individual, we can not do selection or
crossover. Random mutation is all that is left of the GA. 

\subsection{Answer 4}
% p 151
This is a \emph{Constraint Satisfaction Problem}, CSP, and an excellent
candidate for Local Search. Since we are dealing with a linear problem
with linear constraints and intger-only variables we may also use,
\emph{Integer Linear Programming}, ILP, for which there are many
libraries.

However, in this particular problem the solution unfolds in a fairly
straight-forward fashion, as soon as we start to look at the constraints
and it's implications. If we start to look at the column addition
constraints, we soon find that $F$ (which may not be $0$) must be equal
to $1$. So then $A$ must be $0$ and so on, and so on.

\subsubsection{Solution:}
\begin{verbatim}
  H E L P     9 5 6 7
+ F A M E   + 1 0 8 5
---------   ---------
F A L E C   1 0 6 5 2
\end{verbatim}

